<!DOCTYPE html><html><head><meta charset="utf-8"><title>植的博客</title><meta name="viewport" content="width=device-width, initial-scale=1"><link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css">
<link rel="stylesheet" href="/css/base.css">
<script type="text/javascript">(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?ad6863b0ceb3ebc04afed41dc020bd78";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();</script><script type="text/x-mathjax-config">MathJax.Hub.Config({
  tex2jax: {
    inlineMath: [['$','$'], ['\\(','\\)']],
    displayMath: [['$$', '$$'], ['\\[','\\]']],
    processEscapes: true,
    processEnvironments: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre','code'],
    TeX: { equationNumbers: { autoNumber: "AMS" },
         extensions: ["AMSmath.js", "AMSsymbols.js"] }
  }
});</script><script src="//cdn.bootcss.com/mathjax/2.6.1/MathJax.js?config=default"></script><meta name="generator" content="Hexo 4.2.0"><link rel="alternate" href="/atom.xml" title="植的博客" type="application/atom+xml">
</head><body><header><div class="page"><nav><ul class="brand"><li><a href="/">植的博客</a></li></ul><ul class="blog"><!-- List other items on menu.--><li class="menu-item"><a class="on" href="/archives">存档</a></li><li class="menu-item"><a href="/tags">标签</a></li><li class="menu-item"><a href="https://sanduck.github.io/about/" target="_blank" rel="noopener">梦</a></li></ul><ul class="social"><li><a class="fa fa-github" href="https://github.com/yfwz100" target="_blank" rel="noopener"><i class="sr-only">github</i></a></li><li><a class="fa fa-git" href="http://git.oschina.net/zhi" target="_blank" rel="noopener"><i class="sr-only">git</i></a></li><li><a class="fa fa-weibo" href="http://weibo.com/yfwz100" target="_blank" rel="noopener"><i class="sr-only">weibo</i></a></li></ul></nav></div></header><div class="post wrap"><div class="page"><div class="post-heading"><h1>矩阵分解技巧</h1></div><div class="post-body"><p>前段时间了解了一下协同过滤模型，提到了稀疏性的问题，就来看看《Matrix Factorization Techniques for Recommender Systems》中关于矩阵分解的描述是如何来解决的吧。理论上说应该是潜在语义分析中的主题模型的，具体做法在 2006 年以前已经有了。其中提到两种方法：随机梯度下降法和交替最小二乘法，这两个方法还挺有意思的，如有错误请指正。</p>
<h1>问题描述</h1>
<p>假设大家已经了解协同过滤算法了，也知道评分矩阵是怎么一回事。为了简化描述，首先给出问题描述，为了解决潜在因子分解的问题，我们最终要优化如下表达式：</p>
<p>$$ \min_{q^<em>, p^</em>}\sum_{(u,i) \in K} (r_{ui}-q_i^T p_u)^2 + \lambda (|q_i|<sup>2+|p_u|</sup>2) $$</p>
<p>其中集合 $K$ 表示显式给出的提示的 $(u,i)$ 组合，而 $\lambda$ 表示正则化参数。<br>
按惯例，所有小写字母只代表一个数值或向量，这里的 $q_i$ 和 $p_u$  是等维度的向量，其余是数值。</p>
<h2 id="随机梯度下降法（SDG）"><a class="anchor" href="#随机梯度下降法（SDG）">#</a>随机梯度下降法（SDG）</h2>
<p>随机梯度下降法是一种比较简单的解法，具体做法是：</p>
<ol>
<li>
<p>从集合 $K$ 中随机选择某一对 $(u, i)$ ，计算相对误差 $ e_{ui} = r_{ui} - q_i^T p_u $</p>
</li>
<li>
<p>更新两个矩阵：</p>
<p>$$ q_i \leftarrow q_i + \gamma \cdot (e_ui \cdot p_u - \lambda \cdot q_i ) $$</p>
<p>$$ p_u \leftarrow p_u + \gamma \cdot (e_ui \cdot p_u - \lambda \cdot p_u ) $$</p>
</li>
<li>
<p>重复以上过程，最终使得大部分（给出的阈值）的 $e_{ui}=0$ 则结束算法。</p>
</li>
</ol>
<h2 id="交替最小二乘法（ALS）"><a class="anchor" href="#交替最小二乘法（ALS）">#</a>交替最小二乘法（ALS）</h2>
<p>最小二乘……怎么听着这么熟悉？让我们看回原来的优化函数，如果 $q_i^T$  或者 $p_u$  是固定的矩阵，是不是就很熟悉了？那样就是经典的最小二乘法了。可是，$q_i^T$ 和 $p_u$ 都是待优化参数，这样这个问题就不是简单的最小二乘问题了（应该说不是凸优化 convex optimization 问题了）。但是，如果我们每次都固定其中的一项，然后计算另一项，这个问题就迎刃而解了。交替最小二乘法说的就是每次迭代，都交替地优化 $q_i^T$ 和 $p_u$ 使得问题可以以普通的最小二乘法来解。事实上并没有什么黑魔法。</p>
<h1>整合外部信息</h1>
<p>这篇文章另一个有意思的部分是把外部信息引入到矩阵分解算法中。实际上就是修改了优化函数：</p>
<p>$$ \min_{p<sup>*,q</sup><em>,b^</em>} \sum_{(u,i) \in K} (r_{ui} - \mu - b_u - b_i - p_u^T q_i )^2 + \lambda (|p_u|<sup>2+|q_i|</sup>2+b_u<sup>2+b_i</sup>2) $$</p>
<p>这里的技巧就是把需要的外部信息整合为矩阵，然后加入到优化算法中。</p>
<p>对于外部信息，文章提到：</p>
<ol>
<li>偏见：用户评分的标准不一，有些用户总爱评高分，有些用户总爱平低分。</li>
<li>隐式反馈：没看的很明白 。。。参见 Collaborative Filtering for Implicit Feedback Datasets</li>
<li>时变：用户对某商品的偏好是随时间而改变的，因此评分和其他变量，例如偏好，都是时间的函数。</li>
<li>置信水平：对这种评分可信度的评价。</li>
</ol>
<h1>最后</h1>
<p>附上一段 Python 写的用随机梯度下降方法解的矩阵分解算法吧。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">sgd_mf</span><span class="params">(ratings, p=None, q=None, factors=<span class="number">40</span>, g=<span class="number">1e-2</span>, l=<span class="number">1e-6</span>, s=<span class="number">1.0</span>, max_iters=<span class="number">100</span>)</span>:</span></span><br><span class="line">    <span class="string">""" Stochastic Gradient Descent for Matrix Factorization.</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">    :param ratings: the ratings matrix.</span></span><br><span class="line"><span class="string">    :param p: (optional) the P matrix for the first dimension of ratings matrix.</span></span><br><span class="line"><span class="string">    :param q: (optional) the Q matrix for the second dimension of ratings matrix.</span></span><br><span class="line"><span class="string">    :param factors: (optional) the number of latent factors.</span></span><br><span class="line"><span class="string">    :param g: (optional) the learning rate.</span></span><br><span class="line"><span class="string">    :param l: (optional) the regularized coefficient.</span></span><br><span class="line"><span class="string">    :param s: (optional) the number of samples that used to calculate the matrix.</span></span><br><span class="line"><span class="string">    :param max_iters: (optional) the maximum number of iterations.</span></span><br><span class="line"><span class="string">    :return : (optional) the tuple of (P, Q) matrix.</span></span><br><span class="line"><span class="string">    """</span></span><br><span class="line">    rows, cols = ratings.shape</span><br><span class="line">    nz = transpose(nonzero(ratings))</span><br><span class="line">    sn = int(len(nz) * s)</span><br><span class="line">    p = p <span class="keyword">or</span> random.random_sample((rows, factors)) * <span class="number">0.1</span></span><br><span class="line">    q = q <span class="keyword">or</span> random.random_sample((cols, factors)) * <span class="number">0.1</span></span><br><span class="line">    <span class="keyword">for</span> it <span class="keyword">in</span> range(max_iters):</span><br><span class="line">        snz = random.choice(len(nz), sn, replace=<span class="literal">False</span>)</span><br><span class="line">        <span class="keyword">for</span> n, (u, i) <span class="keyword">in</span> enumerate(nz[snz]):</span><br><span class="line">            pu = p[u].copy()</span><br><span class="line">            qi = q[i].copy()</span><br><span class="line">            e = ratings[u, i] - pu @ qi.T</span><br><span class="line">            p[u] = pu + g * (e * qi - l * pu)</span><br><span class="line">            <span class="keyword">assert</span> <span class="keyword">not</span> any(isnan(p[u]) | isinf(p[u])), <span class="string">'%d p Nan/inf: %d %d %d %f'</span> % (n, e, u, i, pu @ qi.T)</span><br><span class="line">            q[i] = qi + g * (e * pu - l * qi)</span><br><span class="line">            <span class="keyword">assert</span> <span class="keyword">not</span> any(isnan(q[i]) | isinf(q[i])), <span class="string">'%d q Nan/inf: %d %d %d %f'</span> % (n, e, u, i, pu @ qi.T)</span><br><span class="line">    <span class="keyword">return</span> p, q</span><br></pre></td></tr></table></figure>
</div><div class="post-meta">由 <span class="author"><a href="mailto: yfwz100@yeah.net">Zhi</a></span> 写于 <span class="date">2016年2月29日</span> ·<span class="tags"><a class="tag" href="/tags/数据挖掘/">数据挖掘</a></span></div><div class="cloud-tie-wrapper" id="cloud-tie-wrapper"></div><script type="text/javascript" src="https://img1.cache.netease.com/f2e/tie/yun/sdk/loader.js"></script><script type="text/javascript">var cloudTieConfig = {
  url: document.location.href, 
  sourceId: "",
  productKey: "2311812cfc39469b8c071ba8f99d562e",
  target: "cloud-tie-wrapper"
};
var yunManualLoad = true;
Tie.loader("aHR0cHM6Ly9hcGkuZ2VudGllLjE2My5jb20vcGMvbGl2ZXNjcmlwdC5odG1s", true);</script><script type="text/javascript" src="https://img1.cache.netease.com/f2e/tie/yun/sdk/loader.js"></script></div></div><footer><div class="page"><address class="author">&copy; Zhi</address><div class="hexo-powered">博客由 <a href="http://www.hexo.io" target="_blank" rel="noopener">Hexo</a> 驱动</div><div class="rss"><a class="fa fa-rss-square" href="/atom.xml"></a></div></div></footer></body></html>